package Sort_06;
import Tree_09.HeapSort_04.HeapSort;
/*
 * @Author 罗
 * @date 2020/3/15 - 11:19 下午
 * 算法的时间复杂度
 *      度量一个程序（算法）执行时间的两种方法
 * (1)事后统计法
 *      这种方法可行，但是有两个问题：
 *      1.要想对设计的算法的运行性能进行评测，需要实际运行该程序
 *      2.所得的时间的统计量依赖于计算机的硬件、软件等运行环境
 *      这种方式需要在同一台计算机的相同状态下运行，才能比较那个算法速度更快
 * (2)事前估计法
 *      通过分析某个算法的时间复杂度来判断那个算法更优
 *
 * 时间频度
 *      一个算法花费的时间与算法中语句的执行次数成正比
 *  那个算法中语句执行次数多，它花费的时间就多
 *  一个算法中的语句执行次数称为语句频度或者时间频度，记为T(n)
 *
 * 随着规模(n)的变大 1.常数项可以忽略
 *                 2.低次项可以忽略
 *                 3.高阶项的系数可以忽略
 *                 4.若高阶项的次数相同，则可以将高阶项消去，取高阶项的系数作为比例
 * 时间复杂度
 *  (1)一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数
 *      用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，
 *      T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的通数量级函数
 *      计作T(n) = O (f(n))，称O(f(n))为算法的渐进时间复杂函数，
 *      简称时间复杂度
 *  (2)T(n)不同，但时间复杂度可能相同
 *      T1(n) = n^2+7n+6
 *      T2(n) = 3n^2+2n+2
 *      他们的T(n) 不同，但是时间复杂度相同都是O(n^2)
 *  (3)计算时间复杂度的方法------------------->T(n) = 3n^2+2n+9
 *      1.用常数1代替运行时间中的所有加法常数--->T(n) = 3n^2+2n+1
 *      2.修改后的运行次数函数中，只保留最高阶项->T(n)= 3n^2
 *      3.去除最高阶项的系数------------------>T(n)= n^2
 *              ------>O(n^2)
 *  (4)常见的时间复杂度（由到大排序）
 *      常数阶     O(1)
 *      对数阶     O(log2n)
 *      线性阶     O(n)
 *      线性对数阶  O(n log2n)
 *      平方阶     O(n^2)  双层嵌套for循环
 *      立方阶     O(n^3)  三层嵌套for循环
 *      k次方阶    O(n^k)  k层嵌套for循环
 *      指数阶     O(2^n)  尽量避免
 *      阶乘       O(n!)  最最麻烦
 *  (5)随着问题规模n的增大，上述的时间复杂度不断增大，算法的执行效率越低
 *      尽量避免指数阶算法
 */


import java.util.Arrays;

public class test {



    public void test() {
        int[] array = new int[8000000];

        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 100000000);
        }
        int[] arrayForMine = Arrays.copyOf(array, array.length);
        int[] arrayForTeacher = Arrays.copyOf(array, array.length);
        int[] arrayForQuick = Arrays.copyOf(array, array.length);
        int[] arrayForMerge = Arrays.copyOf(array, array.length);
        int[] arrayForRadixSort = Arrays.copyOf(array, array.length);
        int[] arrayForHeapSort = Arrays.copyOf(array, array.length);

//        shellSortingOfTeacher(arrayForTeacher);
//        shellSortingOfMine(arrayForMine);
        quickSortTest(arrayForQuick);
        MergeSortTest(arrayForMerge);
//        RadixSortTest(arrayForRadixSort);
        HeapSortTest(arrayForHeapSort);
//        System.out.println(Arrays.toString(arrayForHeapSort));
    }

    /**
     * 测试堆排序
     * @param arrayForHeapSort
     */
    public static void HeapSortTest(int[] arrayForHeapSort){
        long HeapSortStart = System.currentTimeMillis();
        HeapSort.heapSort(arrayForHeapSort);
        long HeapSortCurrentTime = System.currentTimeMillis();
        System.out.println("堆排序法耗时" + (HeapSortCurrentTime - HeapSortStart) + "ms");
//        System.out.println(Arrays.toString(arrayForRadixSort));
    }
    /**
    /**
     * 桶排序测试
     * @param arrayForRadixSort
     */
    public static void RadixSortTest(int[] arrayForRadixSort){
        long RadixSortStart = System.currentTimeMillis();
        RadixSort_08.radixSort(arrayForRadixSort);
        long RadixSortCurrentTime = System.currentTimeMillis();
        System.out.println("基数排序法耗时" + (RadixSortCurrentTime - RadixSortStart) + "ms");
//        System.out.println(Arrays.toString(arrayForRadixSort));
    }
    /**
     * 测试基数排序
     * @param arrayForMergeSort
     */
    public static void MergeSortTest(int[] arrayForMergeSort) {
        long arrayForMergeSortStart = System.currentTimeMillis();
        MergeSorting_07.mergeSorting(arrayForMergeSort, 0, arrayForMergeSort.length - 1, new int[arrayForMergeSort.length]);
        long arrayForMergeSortCurrentTime = System.currentTimeMillis();
        System.out.println("归并排序法耗时" + (arrayForMergeSortCurrentTime - arrayForMergeSortStart) + "ms");
//        System.out.println(Arrays.toString(arrayForMergeSort));
    }

    /**
     * 测试快速排序
     *
     * @param arrayForQuickSort
     */
    public static void quickSortTest(int[] arrayForQuickSort) {
        long quickStart = System.currentTimeMillis();
        QuickSort_06.quickSort(arrayForQuickSort, 0, arrayForQuickSort.length - 1);
        long quickCurrentTime = System.currentTimeMillis();
        System.out.println("快速排序法耗时" + (quickCurrentTime - quickStart) + "ms");
//        System.out.println(Arrays.toString(arrayForQuickSort));
    }

    /**
     * 计算希尔排序法所耗的时间（我写的）
     *
     * @param arrayForShellSorting
     * @version 1.0
     */
    public static void shellSortingOfMine(int[] arrayForShellSorting) {

        long shellStart = System.currentTimeMillis();
        ShellSorting_05.shellSorting(arrayForShellSorting);
        long shellCurrentTime = System.currentTimeMillis();
        System.out.println("我的希尔排序法耗时" + (shellCurrentTime - shellStart) + "ms");

    }

    /**
     * 计算希尔排序法所耗的时间
     *
     * @param arrayForShellSorting
     * @version 2.0
     */
    public static void shellSortingOfTeacher(int[] arrayForShellSorting) {

        long shellStart = System.currentTimeMillis();
        ShellSorting_05.shellSortingByMoving(arrayForShellSorting);
        long shellCurrentTime = System.currentTimeMillis();
        System.out.println("希尔排序法移动法（老师版）耗时" + (shellCurrentTime - shellStart) + "ms");
//        System.out.println(Arrays.toString(arrayForShellSorting));
    }


    /**
     * 计算希尔排序法所耗的时间（老师写的）
     *
     * @param arrayForShellSorting
     */
    public static void shellSortingBySwapping(int[] arrayForShellSorting) {

        long shellStart2 = System.currentTimeMillis();
        ShellSorting_05.shellSortingBySwapping(arrayForShellSorting);
        long shellCurrentTime2 = System.currentTimeMillis();
        System.out.println("老师的希尔排序法耗时" + (shellCurrentTime2 - shellStart2) + "ms");
    }

    /**
     * 计算插入排序法所耗的时间
     *
     * @param arrayForInsertSort
     */
    public static void insertSortingTest(int[] arrayForInsertSort) {

        long insertStart = System.currentTimeMillis();
        Insert_Sort_04.insertSorting(arrayForInsertSort);
        long insertCurrentTime = System.currentTimeMillis();
        System.out.println("插入排序法耗时" + (insertCurrentTime - insertStart) + "ms");
    }


    /**
     * 计算选择排序法所耗的时间
     *
     * @param arrayForSelectSort
     */
    public static void selectSortingTest(int[] arrayForSelectSort) {

        long selectStart = System.currentTimeMillis();
        Select_Sort_03.selectSort(arrayForSelectSort);
        long selectCurrentTime = System.currentTimeMillis();
        System.out.println("选择排序法耗时" + (selectCurrentTime - selectStart) + "ms");
    }

    /**
     * 计算冒泡排序法所耗的时间
     *
     * @param arrayForBubbleSorting
     */
    public static void bubbleSortingTest(int[] arrayForBubbleSorting) {

        long startTime = System.currentTimeMillis();
        Bubble_Sort_02.bubbleSort(arrayForBubbleSorting);
        long currentTime = System.currentTimeMillis();
        System.out.println("冒泡排序法耗时" + (currentTime - startTime) + "ms");
    }
}
